优秀的拆分（power） 【题目描述】 般来说，一个正整数可以拆分成若干个正整数的和。例如，1=1，10=1+2+3+4等。对于正整数n的一种特定拆分，我们称它为“优秀的"，当且仅当在这种拆分下，n被分解为了若干个丕同的2的正整数次幂。注意，一个数x能被表示成2的正整数次幂，当且仅当x能通过正整数个2相乘在一起得到。 例如，10=8+2=23+21是一个优秀的拆分。但是，7=4+2+1=2+21+20就不是一个优秀的拆分，因为1不是2的正整数次幂。现在，给定正整数n，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。 【输入格式】 输入文件名为 power.in. 输入文件只有一行，一个正整数n，代表需要判断的数。 【输出格式】 输出文件名为power.out. 如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。若不存在优秀的拆分，输出"-1"（不包含双引号）。 【样例1输入】 6 【样例1输出】 4 2 【样例1解释】 6=4+2=22+21是一个优秀的拆分。注意，6=2+2+2不是一个优秀的拆分，因为拆分成的3个数不满足每个数互不相同。 【样例2输入】 7 【样例2输出】 -1 【样例3】 见选手目录下的power/power3.in与power/power3.ans 【数据范围与提示】 对于20%的数据，n cout a[++cnt] = base; } n /= 2; base *= 2; } for (int i = cnt; i >= 1; i --) { cout if (sum + b[k] < cnt) { sum += b[k]; k --; } else { cout cin >> q; for (int i = 1; i cin >> q; for (int i = 1; i if (a[x] == 0) a[x] = 1; else a[x] = 0; } int main() { getline(cin, ss); cin >> n; for (int i = 1; i int x; cin >> x; rev(x); // 计算后缀表达式的值 top = 0; string s = ss; s += " “; while (s.find(” “) != -1) { string b = s.substr(0, s.find(” “)); s.erase(0, s.find(” ") + 1); if (b.size() == 0) continue; if (b[0] == ‘x’) { int value = 0; for (int j = 1; j < b.size(); j ++) { value = value*10 + b[j] - ‘0’; } z[++top] = a[value]; } else if (b[0] == ‘!’) { z[top] = !z[top]; } else if (b[0] == ‘&’) { int x1 = z[top–]; int x2 = z[top–]; z[++top] = x1 & x2; } else if (b[0] == ‘|’) { int x1 = z[top–]; int x2 = z[top–]; z[++top] = x1 | x2; } } cout affect(t[i].l); affect(t[i].r); } else if (f[t[i].l] == 0 && f[t[i].r] == 1) { affect(t[i].l); } else if (f[t[i].l] == 1 && f[t[i].r] == 0) { affect(t[i].r); } } else { // |运算 if (f[t[i].l] == 0 && f[t[i].r] == 0) { affect(t[i].l); affect(t[i].r); } else if (f[t[i].l] == 0 && f[t[i].r] == 1) { affect(t[i].r); } else if (f[t[i].l] == 1 && f[t[i].r] == 0) { affect(t[i].l); } } } int main() { char ch; while((ch=getchar())!=’\n’) { int v; if(ch==‘x’) { ++cnt; //新建表达式树的结点 scanf("%d",&v); t[cnt].v = v; z[++top] = cnt; } else if(ch==’ ')continue; else { ++cnt; //新建表达式树的结点 if (ch == ‘!’) { t[cnt].l = z[top–]; t[cnt].v = -1; } else if (ch == ‘&’) { t[cnt].l = z[top–]; t[cnt].r = z[top–]; t[cnt].v = -2; } else { t[cnt].l = z[top–]; t[cnt].r = z[top–]; t[cnt].v = -3; } z[++top] = cnt; } } scanf("%d",&n); for(int i=1; i> q; for (int i = 1; i if (i == n && j == m) { ans = max(ans, s); return; } for (int k = 1; k used[newi][newj] = 1; go(newi, newj, s + a[newi][newj]); used[newi][newj] = 0; } } } int main() { cin >> n >> m; for (int i= 1; i cin >> a[i][j]; } } used[1][1] = 1; go(1, 1, a[1][1]); cout for (int j = 1; j int sum = 0; for (int l = 1; l for (int i = 1; i int sum = 0; for (int l = k; l int sum = 0; for (int l = i; l cin >> n >> m; for (int i= 1; i cin >> a[i][j]; f[i][j] = 0x80000000; } } for (int j = 1; j pre[j][i] = pre[j][i-1] + a[i][j]; } } for (int i = 1; i for (int i = 1; i // 计算k行->i行的区间和 int sum = pre[j][i] - pre[j][k-1]; f[i][j] = max(f[i][j], f[k][j-1] + sum); } // 从（k，j-1）开始走第j列的k行->i行，到达（i，j） for (int k = i + 1; k cin >> n >> m; for (int i = 1; i cin >> a[i][j]; } } for (int i = 0; i f[i][j] = fl[i][j] = fu[i][j] = fd[i][j] = -1e18; } } for (int i = 1; i for (int i = 1; i fu[i][j] = max(fl[i-1][j], fu[i-1][j]) + a[i][j]; } for (int i = n-1; i >= 1; i --) { fd[i][j] = max(fl[i+1][j], fd[i+1][j]) + a[i][j]; } for (int i = 1; i